package com.finance.system.test;


public class Lcs {
    public static void main(String[] args) {
        String X = "abcd",Y = "acd";
        int[][] c = new int[X.length() + 1][Y.length() +1];

        lcs(X,Y,c);
        System.out.println();
        for(int i=0;i<X.length() + 1;i++){
            for(int j=0;j<Y.length() +1;j++){
                System.out.print("  "+c[i][j]);
            }
            System.out.println();
        }
    }

    private static int lcs(String x, String y, int[][] c) {

        for (int i = 1; i <= x.length(); i++) {
            for (int j = 1; j <= y.length(); j++) {

                char xi = x.charAt(i-1),yi = y.charAt(j-1);
                if(xi == yi){
                    c[i][j] = c[i - 1][j-1] + 1;
                    System.out.print(xi);
                }else if(c[i-1][j] >= c[i][j-1]){
                    c[i][j] = c[i-1][j];
                }else c[i][j] = c[i][j-1];
            }
        }

        return 0;
    }


}
